翻訳と辞書 Words near each other ・ Generalized arithmetic progression ・ Generalized assignment problem ・ Generalized audit software ・ Generalized Automation Language ・ Generalized beta distribution ・ Generalized Büchi automaton ・ Generalized canonical correlation ・ Generalized chi-squared distribution ・ Generalized Clifford algebra ・ Generalized complex structure ・ Generalized context-free grammar ・ Generalized continued fraction ・ Generalized coordinates ・ Generalized dihedral group ・ Generalized Dirichlet distribution ・ Generalized distributive law ・ Generalized eigenvector ・ Generalized entropy index ・ Generalized Environmental Modeling System for Surfacewaters ・ Generalized epilepsy with febrile seizures plus ・ Generalized eruptive histiocytoma ・ Generalized erythema ・ Generalized essential telangiectasia ・ Generalized estimating equation ・ Generalized expected utility ・ Generalized extreme value distribution ・ Generalized filtering ・ Generalized first-price auction ・ Generalized flag variety ・ Generalized forces Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Generalized distributive law ： ウィキペディア英語版 Generalized distributive law The generalized distributive law (GDL) is a general message passing algorithm devised by Srinivas M. Aji and Robert J. McEliece. It is a synthesis of the work of many authors in the information theory, digital communications, signal processing, statistics, and artificial intelligence communities. This article is based on a semi-tutorial by Srinivas M. Aji and Robert J. McEliece with the same title.〔 ==Introduction== ''"The distributive law in mathematics is the law relating the operations of multiplication and addition, stated symbolically, $a$ *(b + c) = a *b + a *c; that is, the monomial factor $a$ is distributed, or separately applied, to each term of the binomial factor $b\; +\; c$, resulting in the product $a$ *b + a *c "'' - Britannica As it can be observed from the definition, application of distributive law to an arithmetic expression reduces the number of operations in it. In the previous example the total number of operations reduced from three (two multiplications and an addition in $a$ *b + a *c ) to two (one multiplication and one addition in $a$ *(b + c) ). Generalization of distributive law leads to a large family of fast algorithms. This includes the FFT and Viterbi algorithm. This is explained in a more formal way in the example below: $\backslash alpha(a,\backslash ,\; b)\; \backslash stackrel\; \backslash displaystyle\backslash sum\; \backslash limits\_\; f(a,\; \backslash ,\; c,\; \backslash ,\; b)\; \backslash ,\; g(a,\; \backslash ,\; d,\; \backslash ,\; e)$ where $f(\backslash cdot)$ and $g(\backslash cdot)$ are real-valued functions, $a,b,c,d,e\; \backslash in\; A$ and $|A|=q$ (say) Here we are "marginalizing out" the independent variables ($c$, $d$, and $e$) to obtain the result. When we are calculating the computational complexity, we can see that for each $q^$ pairs of $(a,b)$, there are $q^$ terms due to the triplet $(c,d,e)$ which needs to take part in the evaluation of $\backslash alpha(a,\backslash ,\; b)$ with each step having one addition and one multiplication. Therefore the total number of computations needed is $2\backslash cdot\; q^2\; \backslash cdot\; q^3\; =\; 2q^5$. Hence the asymptotic complexity of the above function is $O(n^5)$. If we apply the distributive law to the RHS of the equation, we get the following: : $\backslash alpha(a,\; \backslash ,\; b)\; \backslash stackrel\; \backslash displaystyle\backslash sum\backslash limits\_\; f(a,\; \backslash ,\; c,\; \backslash ,\; b\; )\; \backslash cdot\; \backslash sum\; \_\; g(a,\backslash ,d,\backslash ,e)$ This implies that $\backslash alpha(a,\; \backslash ,\; b)$ can be described as a product $\backslash alpha\_(a,\backslash ,\; b)\; \backslash cdot\; \backslash alpha\_(a)$ where $\backslash alpha\_(a,b)\; \backslash stackrel\; \backslash displaystyle\backslash sum\backslash limits\_\; f(a,\; \backslash ,\; c,\; \backslash ,\; b\; )$ and $\backslash alpha\_(a)\; \backslash stackrel\; \backslash displaystyle\backslash sum\backslash limits\_\; g(a,\backslash ,\; d,\; \backslash ,e\; )$ Now, when we are calculating the computational complexity, we can see that there are $q^$ additions in $\backslash alpha\_(a,\backslash ,\; b)$ and $\backslash alpha\_(a)$ each and there are $q^2$ multiplications when we are using the product $\backslash alpha\_(a,\backslash ,\; b)\; \backslash cdot\; \backslash alpha\_(a)$ to evaluate $\backslash alpha(a,\; \backslash ,\; b)$. Therefore the total number of computations needed is $q^3\; +\; q^3\; +\; q^2\; =\; 2q^3\; +\; q^2$. Hence the asymptotic complexity of calculating $\backslash alpha(a,b)$ reduces to $O(n^)$ from $O(n^)$. This shows by an example that applying distributive law reduces the computational complexity which is one of the good features of a "fast algorithm". 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Generalized distributive law」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.